﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Problems.Topsort;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ShortestPaths.Acyclic
{
    public class ForwardDagShortestPathsFinder<T> : IShortestPathsFinder<T,double>
    {
        private readonly Func<IDigraph<T>, ITopsorter<T>> _createTopsorter;
        private readonly Func<IEnumerable<T>, IMap<T, double>> _createMap;
        private readonly Func<IEnumerable<T>, IMap<T, T>> _createBackpointersMap;

        public ForwardDagShortestPathsFinder(Func<IDigraph<T>,ITopsorter<T>> createTopsorter = null,
                                            Func<IEnumerable<T>,IMap<T,double>> createMap = null,
                                            Func<IEnumerable<T>,IMap<T,T>> createBackpointersMap = null)
        {
            _createTopsorter = createTopsorter ?? (g => new Topsorter<T>());
            _createMap = createMap ?? (it => AlgoritmiaFactory.Maps<T, double>.Default);
            _createBackpointersMap = createBackpointersMap ?? (it => AlgoritmiaFactory.Maps<T, T>.Default);
        }

        public IEnumerable<KeyValuePair<T, T>> SomeToSomeBackpointers(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var mem = _createMap(g.V);
            var back = _createBackpointersMap(g.V);
            var sourcesList = sources.ToList();
            var targetsList = targets.ToList();
            int left = targetsList.Count;

            foreach(var vertex in _createTopsorter(g).Topsort(g))
            {
                if ( left == 0)
                {
                    break;
                }
                double memv = mem.Get(vertex, double.PositiveInfinity);
           
                if ( sourcesList.Contains(vertex))
                {
                    back[vertex] = vertex;
                    memv = Math.Min(0, memv);
                }

                if ( targetsList.Contains(vertex))
                {
                    left--;
                }
                yield return new KeyValuePair<T, T>(vertex,back[vertex]);
                if ( left > 0)
                {
                    mem.Remove(vertex);
                    back.Remove(vertex);
                    foreach (var s in g.Successors(vertex))
                    {
                        if (!mem.Contains(s))
                        {
                            mem[s] = double.PositiveInfinity;
                        }
                        if ( mem[s] > memv + d(vertex,s) )
                        {
                            back[s] = vertex;
                            mem[s] = memv + d(vertex, s);
                        }
                    }
                }
            }
        }

        public double SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            double mindist = double.PositiveInfinity;
            var mem = _createMap(g.V);
            var sourcesList = sources.ToList();
            var targetsList = targets.ToList();
            int left = targetsList.Count;

            foreach(var vertex in _createTopsorter(g).Topsort(g))
            {
                double memv = mem.Get(vertex, double.PositiveInfinity);
                if (sourcesList.Contains(vertex))
                {
                    memv = Math.Min(0, memv);
                }
                if (targetsList.Contains(vertex))
                {
                    if (memv < mindist)
                        mindist = memv;
                    left--;
                }

                if ( left > 0)
                {
                    mem.Remove(vertex);
                    foreach(var s in g.Successors(vertex))
                    {
                        if ( !mem.Contains(s))
                        {
                            mem[s] = double.PositiveInfinity;
                        }
                        if ( mem[s] > memv + d(vertex,s))
                        {
                            mem[s] = memv + d(vertex, s);
                        }
                    }
                }
                else
                {
                    break;
                }
            }
            return mindist;
        }
    }
}
